
"""
226. 翻转二叉树
"""
from typing import Optional

from com.siyuan.TreeNode import TreeNode


class Solution:

    """方法1：遍历二叉树"""
    def invertTree1(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        self.traverse(root)
        return root

    '''遍历二叉树'''
    def traverse(self, root: Optional[TreeNode]):
        if not root:
            return
        # 前序位置
        self.traverse(root.left)
        # 中序位置
        self.traverse(root.right)
        # 后序位置
        tmp = root.left
        root.left = root.right
        root.right = tmp


    """
    方法2：分解二叉树
    思路：利用函数，先将左子树翻转，再将右子树翻转，最后将左右子树翻转
    """
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        self.invertTree(root.left)
        self.invertTree(root.right)

        tmp = root.left
        root.left = root.right
        root.right = tmp
        return root